public class Solution {
    /*普通的动态规划*/
    public int integerBreak(int n) {

        int[] dp = new int[n+1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            // 这里的易错点dp递推公式弄错
            int curMax = 0;
            for (int j = 1; j < i; ++j) {
                // if (dp[j] * (i - j) > dp[i]) dp[i] = dp[j] * (i - j);
                curMax = Math.max(curMax, Math.max(dp[j] * (i-j), j * (i - j)));
            }
            dp[i] = curMax;


        }
        return dp[n];
    }
    /*方法二：思想将数拆分成只包含2和3的数就能保证最大*/
    public int integerBreak2(int n) {
        if (n < 4) {
            return n - 1;
        }
        int remainder = n % 3;
        int quotient = n / 3;
        if (remainder == 2) {return (int)Math.pow(3, quotient) * 2;}
        else if (remainder == 1) {return (int)Math.pow(3, quotient-1) * 4;}
        else {return (int)Math.pow(3, quotient);}
    }

}
